import java.util.*;

public class Solution {
//    int res;
//    int path;
//    public int subsetXORSum(int[] nums) {
//        // 特殊情况
//        if (nums == null) {
//            return 0;
//        }
//        res = 0;
//        path = 0;
//        subsetSum(nums, 0);
//        return res;
//    }
//
//    public void subsetSum(int[] nums, int index) {
//        // 递归出口
//        if (index >= nums.length) {
//            res += path;
//            return;
//        }
//        // 继续递归
//        // 1. 选当前元素
//        path ^= nums[index];
//        subsetSum(nums, index + 1);
//        // 回溯
//        path ^= nums[index];
//        // 2. 不选当前元素
//        subsetSum(nums, index + 1);
//    }

//    boolean[] vis;
//    List<Integer> path;
//    List<List<Integer>> res;
//    public List<List<Integer>> permuteUnique(int[] nums) {
//        vis = new boolean[nums.length];
//        path = new ArrayList<>();
//        res = new ArrayList<>();
//        Arrays.sort(nums);
//        permute(nums);
//        return res;
//    }
//
//    public void permute(int[] nums) {
//        // 递归出口
//        if (path.size() == nums.length) {
//            res.add(new ArrayList<>(path));
//            return;
//        }
//        // 继续递归
//        for(int i = 0; i < nums.length; i++) {
//            if (!vis[i] && (i == 0 || nums[i] != nums[i - 1] || vis[i - 1] != false)) {
//                path.add(nums[i]);
//                vis[i] = true;
//                permute(nums);
//                // 回溯
//                path.remove(path.size() - 1);
//                vis[i] = false;
//            }
//        }
//    }

    // 存储数字 -> 字符 的映射关系
//    Map<Character, String> hash;
//    StringBuilder path;
//    List<String> res;
//
//    /**
//     * 电话号码的字母组合
//     * @param digits
//     * @return
//     */
//    public List<String> letterCombinations(String digits) {
//        res = new ArrayList<>();
//        path = new StringBuilder();
//        // 处理特殊情况
//        if (digits.length() == 0) {
//            return res;
//        }
//        // 初始化
//        hash = new HashMap<>();
//        hash.put('1', "");
//        hash.put('2', "abc");
//        hash.put('3', "def");
//        hash.put('4', "ghi");
//        hash.put('5', "jkl");
//        hash.put('6', "mno");
//        hash.put('7', "pqrs");
//        hash.put('8', "tuv");
//        hash.put('9', "wxyz");
//        dfs(digits, 0);
//        return res;
//    }
//
//    public void dfs(String digits, int index) {
//        // 递归出口
//        if (index >= digits.length()) {
//            res.add(path.toString());
//            return;
//        }
//        // 继续递归
//        String tmp = hash.get(digits.charAt(index));
//        for(char ch: tmp.toCharArray()) {
//            // 递归
//            path.append(ch);
//            dfs(digits, index + 1);
//            // 回溯
//            path.delete(path.length() - 1, path.length());
//        }
//    }

//    StringBuilder path;
//    List<String> res;
//    int leftNum, rightNum, sum;
//
//    /**
//     * 括号生成
//     * @param n
//     * @return
//     */
//    public List<String> generateParenthesis(int n) {
//        sum = n;
//        path = new StringBuilder();
//        res = new ArrayList<>();
//        dfs();
//        return res;
//    }
//    public void dfs() {
//        // 递归出口
//        if (rightNum == sum) {
//            res.add(path.toString());
//            return;
//        }
//        // 处理左括号
//        if (leftNum >= rightNum && leftNum <= sum) {
//            path.append('(');
//            leftNum++;
//            dfs();
//            // 回溯
//            path.delete(path.length() - 1, path.length());
//            leftNum--;
//        } else {
//            return;
//        }
//        // 处理右括号
//        path.append(')');
//        rightNum++;
//        // 剪枝
//        if (leftNum >= rightNum) {
//            dfs();
//        }
//        path.delete(path.length() - 1, path.length());
//        rightNum--;
//    }
//    public List<List<Integer>> ret;
//    public List<Integer> path;
//    public int n;
//    public int k;
//
//    /**
//     * 组合
//     * @param nn
//     * @param kk
//     * @return
//     */
//    public List<List<Integer>> combine(int nn, int kk) {
//        ret = new ArrayList<>();
//        path = new ArrayList<>();
//        n = nn;
//        k = kk;
//        dfs(1);
//        return ret;
//    }
//    public void dfs(int index){
//        //递归出口
//        if(path.size() == k){
//            ret.add(new ArrayList<>(path));
//            return;
//        }
//
//        for(int i = index; i <= n; i++){
//            path.add(i);
//            dfs(i + 1);//递归
//            path.remove(path.size() - 1);//回溯
//        }
//    }

    int ret, aim;

    /**
     * 目标和
     * @param nums
     * @param target
     * @return
     */
    public int findTargetSumWays(int[] nums, int target) {

        aim = target;
        dfs(nums, 0, 0);
        return ret;
    }
    public void dfs(int[] nums, int pos, int path) {
        // 递归出口
        if (pos == nums.length) {
            if (path == aim) {
                ret++;
            }
            return;
        }
        dfs(nums, pos + 1, path + nums[pos]);
        dfs(nums, pos + 1, path - nums[pos]);
    }


    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {1, 1, 2};
//        solution.subsetXORSum(nums);
   //     solution.permuteUnique(nums);
//        solution.generateParenthesis(3);
    }
}
